import java.util.*;

public class Text {
    //回溯算法
    public List<Integer> path = new LinkedList<>();
    public List<List<Integer>> ret = new LinkedList<>();
    public List<Integer> tmp = new ArrayList<>();

    public void func(int n,int k,int start) {
        if(path.size() == k) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i <= n ; i++) {
            path.add(i);
            func(n,k,i+1);
            path.remove(path.size()-1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        func(n,k,1);
        return ret;
    }
    public void func(int k,int n,int sum,int index) {
        if(k == tmp.size()){
            if(sum == n) {
                ret.add(new ArrayList<>(tmp));
                return;
            }
        }

        for(int i = index; i <= 9; i++) {
            sum += i;
            tmp.add(i);
            func(k,n,sum,i+1);
            sum -= i;
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        func(k,n,0,1);
        return ret;
    }

    //电话号码
    String[] strmap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    String s = "";
    public void func(String digits,int index) {
        if(digits.length() == index) {
            ret.add(s);
            return;
        }

        Character ch = digits.charAt(index);
        String letters = strmap[ch - '0'];

        for(int i = 0; i < letters.length();i++) {
            s = s + letters.charAt(i);
            func(digits,index+1);
            s = s.substring(0,s.length()-1);
        }
    }

    public List<String> letterCombinations(String digits) {
        if(digits.equals("")){
            return ret;
        }
        func(digits,0);
        return ret;
    }

    //39
    public void func(int[] candidates,int target,int sum,int statr) {
        if(sum > target){
            return;
        }
        if(sum == target){
            ret.add(new ArrayList<>(tmp));
            return;
        }

        for(int i = statr;i < candidates.length;i++) {
            sum += candidates[i];
            tmp.add(candidates[i]);
            func(candidates,target,sum,i);
            sum -= candidates[i];
            tmp.remove(tmp.size()-1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        func(candidates,target,0,0);
        return ret;
        Collections.sort();
    }

    //40
    public void func(int[] candidates,int target,int sum,int index,int[] used) {
        if(sum > target) {
            return;
        }
        if(sum == target) {
            ret.add(new ArrayList<>(tmp));
            return;
        }
        for(int i = index; i < candidates.length; i++) {
            if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == 0) {
                continue;
            }
            sum += candidates[i];
            tmp.add(candidates[i]);
            used[i] = 1;
            func(candidates,target,sum,i+1,used);
            sum -= candidates[i];
            tmp.remove(tmp.size()-1);
            used[i] = 0;
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int[] used = new int[candidates.length];
        func(candidates,target,0,0,used);
        return ret;
    }
}
